//给定一个整数数组，找出总和最大的连续数列，并返回总和。 
//
// 示例： 
//
// 输入： [-2,1,-3,4,-1,2,1,-5,4]
//输出： 6
//解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 
//
// 进阶： 
//
// 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 
//
// Related Topics 数组 分治 动态规划 👍 153 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-08 19:32:49
 * @description 面试题 16.17.连续数列
 */
public class ContiguousSequenceLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ContiguousSequenceLcci fun=new ContiguousSequenceLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

		public int maxSubArray1(int[] nums) {
			int pre = 0, maxAns = nums[0];
			for (int x : nums) {
				pre = Math.max(pre + x, x);
				maxAns = Math.max(maxAns, pre);
			}
			return maxAns;
		}
		// todo  线段树


	/*
	*
我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l,r] 区间内的最大子段和，
那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l,r]，我们取
m=[(l+r)/2]
对区间 [l,m] 和 [m+1,r] 分治求解。
当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。
这个时候我们考虑如何通过 [l,m] 区间的信息和 [m+1,r] 区间的信息合并成区间 [l,r] 的信息。最关键的两个问题是：

我们要维护区间的哪些信息呢？
我们如何合并这些信息呢？
对于一个区间 [l,r]，我们可以维护四个量：

lSum 表示 [l,r] 内以 l 为左端点的最大子段和
rSum 表示 [l,r] 内以 r 为右端点的最大子段和
mSum 表示 [l,r] 内的最大子段和
iSum 表示 [l,r] 的区间和
以下简称 [l,m] 为 [l,r] 的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l,r] 的信息）？对于长度为 1 的区间 [i,i]，四个量的值都和 nums[i] 相等。对于长度大于 1 的区间：

首先最好维护的是 iSum，区间 [l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，
要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。

对于 [l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，
要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。

当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。
我们可以考虑 [l,r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，
也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；
它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。

	* */
	public class Status {
		public int lSum, rSum, mSum, iSum;

		public Status(int lSum, int rSum, int mSum, int iSum) {
			// 以 l 为左端点的最大子段和
			this.lSum = lSum;
			// 以 r 为右端点的最大子段和
			this.rSum = rSum;
			// [l,r] 内的最大子段和
			this.mSum = mSum;
			// 区间和
			this.iSum = iSum;
		}
	}

	public int maxSubArray(int[] nums) {
		return getInfo(nums, 0, nums.length - 1).mSum;
	}

	public Status getInfo(int[] a, int l, int r) {
		if (l == r) {
			return new Status(a[l], a[l], a[l], a[l]);
		}
		// 取中点
		int m = (l + r) >> 1;
		// 左子树
		Status lSub = getInfo(a, l, m);
		// 右子树
		Status rSub = getInfo(a, m + 1, r);
		//
		return pushUp(lSub, rSub);
	}

	public Status pushUp(Status l, Status r) {
		int iSum = l.iSum + r.iSum;
		int lSum = Math.max(l.lSum, l.iSum + r.lSum);
		int rSum = Math.max(r.rSum, r.iSum + l.rSum);
		int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
		return new Status(lSum, rSum, mSum, iSum);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
